package com.zk.algorithm.linkedlist;

import com.zk.algorithm.Utils;
import com.zk.algorithm.annotation.Easy;
import com.zk.algorithm.annotation.LeetCodeExplore;
import com.zk.algorithm.bean.ListNode;
import com.zk.algorithm.factory.ListFactory;

import java.util.Stack;

/**
 * @author zk
 */
@LeetCodeExplore
@Easy
public class PalindromeLinkedList {

    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }

        Stack<ListNode> stack = new Stack<>();

        int size = size(head);
        ListNode slow = head;

        while (stack.size() < size / 2) {
            stack.push(slow);
            slow = slow.next;
        }

        // 奇数的单链表，再往前跑一个
        if (size % 2 == 1) {
            slow = slow.next;
        }

        while (slow != null) {
            if (stack.pop().val != slow.val) {
                return false;
            }

            slow = slow.next;
        }

        return true;
    }

    public int size(ListNode head) {
        int len = 0;

        while (head != null) {
            head = head.next;
            len++;
        }

        return len;
    }

    public static void main(String...args) {
        Utils.println(new PalindromeLinkedList().isPalindrome(ListFactory.create(new int[]{1})));
        Utils.println(new PalindromeLinkedList().isPalindrome(ListFactory.create(new int[]{2,2})));
        Utils.println(new PalindromeLinkedList().isPalindrome(ListFactory.create(new int[]{1,2,3,3,2,1})));
        Utils.println(new PalindromeLinkedList().isPalindrome(ListFactory.create(new int[]{1,2,3,4,3,2,1})));
    }

}
